package dp;

public class _21_213_打家劫舍Ⅱ {
    public int rob(int[] nums) {
    	if(nums.length == 0) {
    		return 0;
    	}
    	if(nums.length == 1) {
    		return nums[0];
    	}
    	
    	if(nums.length == 2) {
    		return Math.max(nums[0], nums[1]);
    	}
    	
    	int rob1[] = new int[nums.length - 1];
    	int rob2[] = new int[nums.length - 1];
    	
    	// 是环形的，因此如果选第一个，那么最后一个就选不了，如果选第二个，那么第一个就选不了
    	// 所以只需要对数组进行分割，分别求最优解，两个最优解的最大值就是最终最优解
    	for(int i = 0; i < nums.length - 1; i++) {
    		rob1[i] = nums[i];
    	}
    	
    	for(int i = 1; i < nums.length; i++) {
    		rob2[i-1] = nums[i];
    	}

    	
    	return Math.max(money(rob1), money(rob2));
    }
    
    public int money(int nums[]) {
    	int dp[] = new int[nums.length];
    	dp[0] = nums[0];
    	dp[1] = Math.max(nums[0], nums[1]);
    	for(int i = 2; i < nums.length; i++) {
    		dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
    	}
    	
    	return dp[nums.length - 1];
    }
    
    public static void main(String[] args) {
    	int nums[] = {1,2,3};
		System.out.println(new _21_213_打家劫舍Ⅱ().rob(nums));
	}
}
